In raster displays, the objects displayed on the screen of a cathode ray tube (CRT) are made up of picture elements or pixels. The raster is simply a matrix of pixels covering the entire screen. A set of horizontal raster lines made up of individual pixels forms the image which is scanned out sequentially one raster line at a time. The information needed to form the image is stored in a bit map containing at least one bit for each pixel.
The bit map is made up of a dynamic random access memory (DRAM) array having numerous cells which can each contain one bit of information. Each DRAM cell can be addressed by the proper selection of its row and column location. When the bit map is used to control the screen image of a CRT in a simple graphics display each DRAM cell determines the state, either on or off, of one pixel. A high resolution CRT may have, for example, a width of 1024 and a length of 768 pixels.
FIG. 1 depicts a display screen 20 having five rows and ten columns of pixels which display a trapezoid 22. Of course, a standard high definition screen may have 1024.times.768 pixels. The first line 24 of trapezoid 22 consists of filled or "on" pixels in columns 4, 5 and 6 of row 2. Array 30 of FIG. 2 depicts the data that would be stored in a bit map which controls the display screen 20 in FIG. 1. The bit map which holds the data shown in FIG. 2 has 10 columns and 5 rows of DRAM cells which each hold one bit of data, either a 1 or a 0. Each DRAM cell of such a bit map corresponds to 1 pixel of screen 20 so that a 1 bit stored in a DRAM cell causes the appropriate pixel to be on or filled and a 0 bit causes the appropriate pixel to be off or cleared. For instance, in a bit map, the DRAM cells which contain the data shown in array 30 hold a 1 in columns 4, 5 and 6 of row 2, causing pixels 4, 5 and 6 in row 2 of screen display 20 to be on. To clear or erase the first line 24 of trapezoid 20, the 1 bits in row 2 of array 30 must be set to 0.
When a graphics program operator desires to fill or clear some portion of the screen, such as the first row 24 of trapezoid 20, a prior art method of doing so performs a memory operation for each pixel being changed. Each cell of the bit map corresponding to the appropriate pixel must be individually addressed and the appropriate data, 1 or 0, written into that cell. For instance, to clear first line 24 of trapezoid 22, three memory operations would be required, but to clear one horizontal line of a high resolution CRT screen 1024 memory operations would be required. This method of clearing a screen portion is unsatisfactorily slow.
In 1986, at the IEEE International Solid-State Circuits Conference, Whitesides et al. presented the method "Flash Write" which is capable of improving the speed for clearing a screen in certain circumstances. "Flash Write" addresses an entire row of the bit map corresponding to an entire line of pixels and writes the same data to each cell of the bit in single cycle. "Flash Write" allows clearing of an entire screen of pixels in 1/1024 the amount of time required for the prior art method described above (for a screen 1024 pixels wide). However, "Flash Write" encompasses a major drawback in that only an entire line of the screen may be cleared in this manner. Segments of the line must be cleared by erasing each pixels individually, necessitating addressing each bit map cell. For example, "Flash Write" could not be used to generate polygon 32 of FIG. 3 from trapezoid 22 by clearing columns 3 and 4 of row 3 and columns 2, 3 and 4 of row 4 of screen 20 and array 30.
Texas Instruments developed another improvement for clearing screen portions called "4.times.4 Block Write" as part of the TMS44C251 multiport Video RAM. The rows of the device each have four bit words enabling 4 bits to be addressed with each memory cycle. Because each bit still corresponds to one pixel, clearing a line segment can be accomplished in 1/4 the number cycles required to clear the same segment by addressing one cell at a time. "Block Write" also allows four bits of data present in an on-chip color data register to be written to any combination of four adjacent column address locations. By addressing four column locations at once and a row containing four bit words, 16 bits of data can be written to the bit map memory during one memory cycle, corresponding to clearing or filling a 16 pixel block of the screen. "Block Write" and four bit words have the disadvantage, however, that numerous memory cycles are still required to clear or fill a large portion of the screen, thereby significantly slowing the procedure.
The TI device and other prior art memories are also equipped with a write mask register which provides a persistent write per bit mode without repeated mask loading. The mask register contains one bit for each pixel in one line of the screen and one row of the bit map. A single mask register can be used for multiple rows of the bit map and each row is acted upon independently. In order to clear a line segment the column input data for the mask register will be chosen so that when the mask register is ANDed with the row of interest, the appropriate cells of the bit map will be set to zero so that the corresponding pixels will be cleared. When the portion of the screen to be cleared or filled is a rectangle, the first and last pixel of the rectangle will be the same for each line of the screen and, therefore, the mask register will be the same for each row of the bit map. By repeatedly using the same mask register, a rectangle can be cleared substantially faster as compared to the method in which each bit is individually addressed. When the rectangle is completely cleared, the mask is simply disabled.
Defining a mask register requires individual serial input for each bit of the mask. If the screen portion to be cleared or filled is not a rectangle but rather an irregularly shaped polygon, the first and last pixels of the polygon may be different in each line. In this case the mask register must be updated before being ANDed with each row of the bit map, requiring the same number of memory cycles as bits in each row, in many cases 1024, significantly lengthening the time needed to clear or fill the irregular polygon.
In 1984, NEC, as part of industry and customer presentations of advanced graphics described a video memory with multiple serial registers that included a mode for writing to whole segments of the bit map memory in a single memory cycle. In this mode, a bit map row is divided into 8 equal length segments, each segment being directly mapped from the column address field. When a segment is addressed, the entire segment can be written to in one cycle, requiring only eight cycles to write an entire row of the bit map and to clear or fill a whole line of pixels. However, because each bit of a segment will contain the same data when the entire segment is written at one time, bits corresponding to pixels to be cleared or filled which lie outside an integral number of segments must be addressed and changed individually. The one eighth row length of the segments is too coarse to be optimal for most applications. As the more desirable single bit resolution requires a unique clock cycle or operation to set the mask register for each data bit is undesirably slow, neither concept was implemented in a product.
The question presented by the prior art then is how to clear or fill an irregularly shaped object displayed on a CRT screen as quickly as possible.